سیستمهای چند عامله سیستمهای محاسباتی هستند که در آن چندین عامل جهت رسیدن به یک هدف خاص با هم در تعامل هستند و با هم کار می کنند. دلیل پیدایش اینگونه سیستمها وجود موقعیتهایی است که در آن یک مسأله بایستی در یک مد توزیع شده حل شود. به عنوان مثال در شرایطی که استفاده از یک کنترل کننده مرکزی ممکن نیست و یا اینکه میخواهیم استفاده مناسبی از منابع توزیع شده و یا امکانات محاسباتی داشته باشیم. با اینکه زمان زیادی از معرفی این گونه سیستم‌ها نمی‌گذرد ولی استفاده از روش‌های طراحی بر اساس عامل یکی از موفق‌ترین راه‌حل‌های موجود بوده و حاصل این شیوه طراحی یعنی سیستم‌ حل مسائل به صورت توزیع‌شده از بهترین سیستم‌ها به شمار می‌آید و به عنوان ابزار جدیدی برای حل انواع فرآیندهای انسانی شناخته می‌شود. مسأله ارضاء محدودیت توزیع شده سالهاست که در حوزه تحقیق سیستمهای چند عامله مورد توجه زیادی قرار گرفته است. و این مسأله بدان علت است که بسیاری از مسائل اعم از مسائل کلاسیکی همانند مسأله n-وزیر و رنگ آمیزی گراف گرفته و تا مسائل کاربردی بزرگ دنیای واقعی همچون زمانبندی و برنامه ریزی و تخصیص منابع میتوانند برای حل شدن به عنوان یک مسأله مسأله ارضاء محدودیت توزیع شده فرموله شوند. بنابراین ارائه یک شیوه جدید و یا اصلاح شیوه های فعلی تاثیر زیادی بر دامنه تحقیقاتی این فیلد میگذارد. آنچه در این پایاننامه ارائه میشود ارائه تکنیکی جدید برای حل مسائل ارضاء محدودیت توزیع شده است. این تکنیک جدید محدودیتها را در یک سیستم که ترکیبی از سیستمهای توزیع شده و متمرکز است اداره و کنترل میکند که با بهره گیری از یک سری ویژگیهای خاص تعریف شده از سیستمهای ترکیبی دیگر موجود متمایز میشود. نتایج حاصله نشان می دهد که این الگوریتم در مسائل با مقیاس بزرگ کارایی خوبی خواهد داشت و تقریبا یک پیچیدگی زمانی خطی را با افزایش مقیاس مسأله به دست میآورد. همچنین مقایسه این روش با چند روش دیگر بهبود عملکرد این روش را در پارامترهای مختلف نسبت به دیگر روشها نشان میدهد.

فهرست مطالب

عنوان صفحه

فصل اول: مقدمه

مسئله ارضاء محدودیت(CSP: Constraint Satisfaction Problem) …………………………………….. 3
- تعریف مسئله ارضاء محدودیت(CSP: Constraint Satisfaction Problem):……………………………………….. 3
- الگوریتمهای کلاسیک مسائل ارضاء محدودیت…………………………………………………………………………………………………….. 5
- CSP به عنوان یک مسئله جستجو…………………………………………………………………………………………………………………….. 7
- بهبود کارآیی الگوریتمهای جستجوتوسط توابع اکتشافی یا به عبارتی هیوریستیک ها………………………………………. 8
- محدودیتهای ویژه………………………………………………………………………………………………………………………………………………… 12
- کاربرد جستجوهای محلی در حل مسائل ارضاء محدودیت……………………………………………………………………………….. 12
- ساختار مسئله………………………………………………………………………………………………………………………………………………………. 12
سیستمهای چند عامله………………………………………………………………………………………………………………………….. 14
حل مسائل CSP توسط سیستمهای چند عامله؛(DCSP)………………………………………………………………. 16

فصل دوم: مروری بر تحقیقات پیشین

مرور کلی………………………………………………………………………………………………………………………………………………. 19
الگوریتمهای هرس دامنه……………………………………………………………………………………………………………………… 22
- الگوریتم تصفیه…………………………………………………………………………………………………………………………………………………… 22
- الگوریتم فرا استدلال………………………………………………………………………………………………………………………………………….. 25
الگوریتمهای اکتشافی…………………………………………………………………………………………………………………………… 27
- الگوریتم عقبگرد نامتقارن………………………………………………………………………………………………………………………………………. 28
- الگوریتم الزام ضعیف نامتقارن…………………………………………………………………………………………………………………………………. 32
الگوریتمهایی که از ترکیب روشهای متمرکز و توزیع شده استفاده می کنند…………………………………….. 33
- الگوریتم APO……………………………………………………………………………………………………………………………………………………….. 33
الگوریتمهای ناقص……………………………………………………………………………………………………………………………….. 37
- الگوریتم DBA …………………………………………………………………………………………………………………………………………………… 37
- الگوریتمهای مبتنی بر کلونی مورچه ها در حل مسائل ارضاء محدودیت توزیع شده…………………………………………. 37

فصل سوم: طراحی و پیاده سازی روشهای پیشنهادی برای مسائل DCSP و بررسی نتایج حاصله

معیارهای ارزیابی کیفیت روشهای حل مسائل ارضاء محدودیت توزیع شده…………………………………. 44

3-1-1- میانگین زمان اجرای الگوریتم با افزایش مقیاس مسأله………………………………………………………………………………………. 45

3-1-2- میانگین تعداد چرخه های اجرا شده تا رسیدن به یک راه حل ………………………………………………………………………….. 45

3-1-3- تعداد پیام های ارسال و دریافت شده……………………………………………………………………………………………………………………. 45

3-1-4- NCCC …………………………………………………………………………………………………………………………………… 45

3-1-5- قانونی و کامل بودن………………………………………………………………………………………………………………………………………………… 46

محکها و مجموعه داده ای مورد استفاده برای آزمایشات………………………………………………………………. 45

3-2-1- مسأله n-وزیر ……………………………………………………………………………………………………………………………………………………….. 46

3-2-2- مسأله رنگآمیزی گراف ……………………………………………………………………………………………………………………………………….. 47

3-2-3- مسائل زمانبندی …………………………………………………………………………………………………………………………………………………… 48

3-2-4- مسائل ارضاء محدودیت باینری ……………………………………………………………………………………………………………………………. 51

3-3- طراحی و پیاده سازی روشهای پیشنهادی و نتایج حاصله از آنها………………………………………………………. 52

3-3-1- استفاده از ترکیب الگوریتمهای تکاملی و سیستمهای چندعامله برای حل مسائل ارضاء محدودیت ……………… 52

3-3-2- قدرت مورچه ها در حل مسائل ارضاء محدودیت توزیع شده……………………………………………………………………………… 60

فصل چهارم: روش جدید ارائه شده

4-1- مروری بر مفاهیم و موضوعات مورد بحث دراین روش پیشنهادی…………………………………………………….. 69

توصیف مسائل ارضاء محدودیت توزیع شده؛(DCSP) ……………………………………………………………………………….. 69
تعریف محدودیت Alldiff یا Alldifferent ………………………………………………………………………………………………. 70
توابع اکتشافی …………………………………………………………………………………………………………………………………………………… 70

تقسیم بندی الگوریتم های مطرح شده برای مسائل DCSP ……………………………………………………………. 71

4-3- توصیف روش جدید ارائه شده و جزئیات پیاده سازی آن…………………………………………………………………… 73

4-4- حل یک مثال با استفاده از این الگوریتم…………………………………………………………………………………………….. 80

4-5- ارزیابی و مقایسه الگوریتم ما با دیگر روشها………………………………………………………………………………………. 82

4-6- نتیجه گیری و برشمردن مزایا و معایب این روش…………………………………………………………………………….. 84

فصل پنجم: نتیجه گیری

5-1- نتیجه گیری……………………………………………………………………………………………………………………………………… 87

5-2- پیشنهادات و کارهای آینده………………………………………………………………………………………………………………. 89

فهرست منابع……………………………………………………………………………………………………………………….. 90

فهرست تصاویر

عنوان صفحه

شکل 1-1 مثالی از مساله CSP [4] …………………………………………………………………………………………………………………. 4

شکل 1-2 یک طرح جامع از به کار بردن تکنیکهای ارضاء محدودیت برای حل مسائل [54] ……………………….. 5

شکل 1-3 (الف) نواحی استرالیا (ب) عملکرد توابع اکتشافی مختلف بر روی این نقشه [2] …………………………………………… 11 شکل 1-4 زیرمسأله های مستقل در گراف محدودیت [2] ……………………………………………………………………………… 13

شکل 1-5 کاهش گراف محدودیت به درخت توسط حذف گرهها [2] ………………………………………………………….. 13

شکل 1-6 کاهش گراف محدودیت به درخت توسط تجزیه گراف [2] ……………………………………………………………. 14

شکل 1-7 یک شبکه حسگر واقعی برای مانیتور کردن محیط داخلی یک ساختمان[4] ………………………………. 15

شکل 2-1 یک طبقه بندی از الگوریتمهای مطرح در حل مسائل DCSP ………………………………………………………. 20

شکل 2-2 چهار حالت مختلف از مسئله کلاسیک رنگ آمیزی گراف و نتیجه پیاده سازی الگوریتم تصفیه برای هر یک از این مسائل[4] ……………………………………………………………………………………………………………………………………. 24

شکل 2-3 سیکل 1 الگوریتم ABT بر روی مسئله 4 وزیر[4] ………………………………………………………………………… 29

شکل 2-4 سیکل 2 از الگوریتم ABT بر روی مسئله 4وزیر[4] ……………………………………………………………………… 29

شکل 2-5 سیکل 3 از الگوریتم ABT بر روی مسئله 4 وزیر[4] …………………………………………………………………….. 30

شکل 2-6 سیکل 4 و 5 از الگوریتم ABT بر روی مسئله 4وزیر[4] ……………………………………………………………… 30

شکل 2-7 سیکل 6 از الگوریتم ABT بر روی مسئله 4وزیر[4] ……………………………………………………………………… 31

شکل 2-8 سیکل 7 و 8 از الگوریتم ABT بر روی مسئله 4وزیر[4] ………………………………………………………….. 31

شکل 2-9 سیکل 9 از الگوریتم ABT بر روی مسئله 4وزیر[4] ……………………………………………………………………… 31

شکل 2-10 سیکل 10 از الگوریتم ABT بر روی مسئله 4وزیر [4] ……………………………………………………………… 32

شکل 2-11 الگوریتم APO [22] ……………………………………………………………………………………………………………………. 35

شکل 2-12 مثالی از گراف ساختار [44] …………………………………………………………………………………………………………. 39

شکل 2-13 ساختن یک گراف برای یک مسأله با سه متغیر …………………………………………………………………………… 40

شکل 3-1 جهت حرکات ممکن یک مهره وزیر در یک صفحه شطرنج ……………………………………………………………. 46

شکل 3-2 یک جواب برای مسأله 8-وزیر …………………………………………………………………………………………………………. 47

شکل 3-3 مثالی از رنگ آمیزی گراف(یک رنگ آمیزی از گراف معروف پترسن) …………………………………………… 48

شکل 3-4 مثالی از مساله CSP [4] …………………………………………………………………………………………………………………. 52

شکل 3-5 مدل فرض شده از محیط شبکه مانند عاملها[3] ……………………………………………………………………………. 53

شکل 3-6 میانگین زمان اجرای الگوریتم MAEA-CSPs در حل مسأله n-وزیر [3] ……………………………………. 58

شکل 3-7 مقایسه الگوریتم MAEA-CSPs با 4 الگوریتم دیگر با معیارهای SR، ME و AES [4] ……………. 59

شکل 3-8 مقایسه دو الگوریتم DBA و ABT با الگوریتم پیشنهادی مورچه ها بر روی مساله رنگ آمیزی گرافی با تراکم 2 ، بر اساس نسبت تغییر سایز مسأله به تعداد پیامها ………………………………………………………………………… 63

شکل 3-9 مقایسه دو الگوریتم DBA و ABT با الگوریتم پیشنهادی مورچه ها بر روی مساله رنگ آمیزی گرافی با تراکم 2 ، بر اساس نسبت تغییر سایز مسأله به معیار مقایسه NCCC ………………………………………………………… 63

شکل 3-10 مقایسه دو الگوریتم DBA و ABT با الگوریتم پیشنهادی مورچه ها بر روی مساله رنگ آمیزی گرافی با تراکم .32 ، بر اساس نسبت تغییر سایز مسأله به تعداد پیامها …………………………………………………………. 63

شکل 3-11 مقایسه دو الگوریتم DBA و ABT با الگوریتم پیشنهادی مورچه ها بر روی مساله رنگ آمیزی گرافی با تراکم 2.3 ، بر اساس نسبت تغییر سایز مسأله به معیار مقایسه NCCC ………………………………………….. 64

شکل 3-12 مقایسه دو الگوریتم DBA و ABT با الگوریتم پیشنهادی مورچه ها بر روی مساله رنگ آمیزی گرافی با تراکم .72 ، بر اساس نسبت تغییر سایز مسأله به تعداد پیامها …………………………………………………………. 64

شکل 3-13 مقایسه دو الگوریتم DBA و ABT با الگوریتم پیشنهادی مورچه ها بر روی مساله رنگ آمیزی گرافی با تراکم 2.7 ، بر اساس نسبت تغییر سایز مسأله به معیار مقایسه NCCC ………………………………………….. 65

شکل 4-1 یک طبقه بندی از الگوریتمهای مطرح در حل مسائل DCSP ………………………………………………………. 72

شکل 4-2 مرحله 1 تا 4 از الگوریتم DACA ………………………………………………………………………………………………….. 80

شکل 4-3 مرحله 5 از الگوریتم DACA ………………………………………………………………………………………………………….. 81

شکل 4-4 مرحله پایانی الگوریتم DACA ……………………………………………………………………………………………………….. 82

شکل 4-5 میانگین زمان اجرای الگوریتم DACA در اجرای مسأله n-وزیر با افزایش n از 4 تا 10⁴ در گامهای 50 تایی ………………………………………………………………………………………………………………………………………………………………. 82

فهرست جداول

عنوان صفحه

جدول 3-1 نتایج بدست آمده از آزمایش MAEA-CSPs بر روی مسائل ارضاء محدودیت باینری …………… 59

جدول 3-2 مقادیر متفاوت از تعداد مورچه ها برای سایزها و تراکمهای متفاوت …………………………………………….60

جدول4-1 مقایسه الگوریتم پیشنهادی ما با دو روش دیگر از لحاظ تعداد سیکلهای مورد نیاز برای حل ……… 82

جدول4-2 مقایسه روش پیشنهادی ما با روش ERA از لحاظ میانگین زمان اجرا ……………………………………….. 82

مقدمه

از سال 1974، مسائل ارضاء محدویت (CSP[1]) در مسأله پردازش تصویر^{^[2]} پیشنهاد شد. پس از آن CSP به طور گسترده در بسیاری از حوزه های هوش مصنوعی و علوم کامپیوتر به عنوان یک روش حل مهم مورد استفاده قرار گرفته است. از مسأله چند وزیر^{^[3]} و رنگ آمیزی گراف^{^[4]} گرفته و دیگر مسائل کلاسیک گرفته تا زمانبندی^{^[5]} و تخصیص منابع^{^[6]} و دیگر مسائل کاربردی بزرگ میتوانند برای حل شدن به عنوان یک مسأله CSP فرموله شوند. بعد از سال 1990 با جایگزین شدن زبان برنامه نویسی عمومی به جای زبان برنامه نویسی منطقی مسأله ارضاء محدودیت کاربرد CSP برای حل مسائل بسیار بهبود یافت [1]. یک CSP، با یک مجموعه از متغیرها، دامنه ای برای هر یک از آنها و محدودیتهایی در مقادیری که متغیرها ممکن است به صورت همزمان به خودشان بگیرند، تعریف میشوند. نقش الگوریتمهای ارضاء محدودیت، نسبت دادن مقادیری به متغیرهاست به نحوی که با تمام محدودیتها سازگاری داشته باشد یا مشخص کند که هیچ انتسابی امکانپذیر نیست. امروزه تکنیکهای ارضاء محدودیت در حوزه های مختلفی از جمله بینایی ماشین، پردازش زبانهای طبیعی، اثبات قضایا، زمانبندی و… به کار میروند [4].

برای دانلود متن کامل پایان نامه اینجا کلیک کنید